package com.sgg.datastructure.stack;

import cn.hutool.core.util.StrUtil;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

public class 表达式 {
    public static List<String> 中缀转后缀(String expression) {
        Stack<String> operate = new Stack<>();
        List<String> result = new ArrayList<>();//可以用arraylist替代
        List<String> split = toInfixExpressionList(expression);//没有考虑超过2位数的数字拼接
        for (String str : split) {
            if (StrUtil.isNumeric(str)) {
                result.add(str);
            } else if (isOperate(str)) {
                while (true) {
                    if (operate.isEmpty() || StrUtil.equals(operate.peek(), "(")) {
                        operate.push(str);
                        break;
                    } else if (isPriority(str, operate.peek())) {
                        operate.push(str);
                        break;
                    } else {
                        String pop = operate.pop();
                        result.add(pop);
                    }
                }
            } else if (StrUtil.equals("(", str)) {
                operate.push(str);
            } else if (StrUtil.equals(")", str)) {
                String ele;
                while (true) {
                    ele = operate.pop();
                    if (StrUtil.equals(ele, "(")) {
                        break;
                    } else {
                        result.add(ele);
                    }
                }
            } else {
                throw new RuntimeException("参数有误");
            }
        }
        while (!operate.isEmpty()) {
            String pop = operate.pop();
            result.add(pop);
        }
        return result;
    }

    private static boolean isPriority(String str, String peek) {
        return getScore(str) > getScore(peek);
    }

    private static int getScore(String str) {
        switch (str) {
            case "+":
            case "-":
                return 1;
            case "*":
            case "/":
                return 2;
            default:
                throw new RuntimeException("参数有误");
        }
    }


    public static boolean isOperate(String str) {
        List<String> list = Arrays.asList("+", "-", "*", "/");
        return list.contains(str);
    }

    public static List<String> toInfixExpressionList(String expression) {
        List<String> result = new ArrayList<>();
        String ele = "";
        String[] split = StrUtil.split(expression, 1);
        for (String raw : split) {
            if (StrUtil.isNumeric(raw)) {
                ele += raw;
            } else {
                if (StrUtil.isNotBlank(ele)) {
                    result.add(ele);
                    ele = "";
                }
                result.add(raw);
            }
        }
        if (StrUtil.isNotBlank(ele)) {
            result.add(ele);
        }
        return result;
    }


    public static void main(String[] args) {
        String middle = "1+((2+3)*41)-20";
        List<String> ex = 中缀转后缀(middle);
        System.out.println(ex);
        System.out.println(后缀表达式计算器.cal(StrUtil.join(StrUtil.SPACE, ex)));
    }
}
